package KnapsackProblem;
import java.util.*;
/**
 * Enjoy programming!!!
 * Time: 2021/11/1 -  20:34
 */
public class KnapsackProblem00 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();//输入背包可装个数
        int V = in.nextInt();//容量
        int[] v = new int[N + 1];//单个体积
        int[] w = new int[N + 1];//单个价值
        int[][] dp = new int[N + 1][V + 1];//二维数组dp用来存放价值
//        dp[0][0] = 0;
        for (int i = 1; i < N + 1; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        for (int i = 1; i <= N; i++){//i不仅代表行，还代表第i个物品
            for (int j = 1; j <= V; j++){//j代表此时背包的最大容量
                if (j >= v[i])
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
                else dp[i][j] = dp[i - 1][j];
            }
        }
        System.out.println(dp[N][V]);
        for (int[] r : dp) {
            for (int d : r)
                System.out.print(d);
            System.out.println();
        }

    }
}
